package LC;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.com/problems/pascals-triangle-ii/description/
 * Given an index k, return the kth row of the Pascal's triangle.
 * For example, given k = 3,
 * Return [1,3,3,1].
 * Note:
 * Could you optimize your algorithm to use only O(k) extra space?
 */
public class LC_119_PascalsTriangleII_Math_Loop {
    public static void main(String[] args) {
        List<Integer> row = Solution.getRow(5);
        System.out.println(row);
    }

    static class Solution {
        static List<Integer> getRow(int rowIndex) {
            rowIndex++;
            if (rowIndex < 0) return null;
            List<Integer> result = new ArrayList<>(rowIndex);
            if (rowIndex >= 1) result.add(1);
            if (rowIndex >= 2) result.add(1);
            int line = 0;
            int prev;
            if (rowIndex >= 3) {
                int[][] data = new int[2][rowIndex];
                data[0][0] = 1;
                data[1][0] = 1;
                data[1][1] = 1;
                for (int i = 2; i < rowIndex; i++) {
                    line = i % 2;
                    prev = (i - 1 + 2) % 2;
                    for (int j = 1; j < i; j++) data[line][j] = data[prev][j - 1] + data[prev][j];
                    data[line][i] = 1;
                }
                result.clear();
                for (int i = 0; i < rowIndex; i++)
                    result.add(data[line][i]);
            }
            return result;
        }
    }
}